package math;

/**
 * 我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。
 * <p>
 * 比方说，"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是 好数字，因为 3 在偶数下标处但不是偶数。
 * 给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。
 * <p>
 * 一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。
 * <p>
 * 示例 1：
 * 输入：n = 1
 * 输出：5
 * 解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。
 * <p>
 * 示例 2：
 * 输入：n = 4
 * 输出：400
 * <p>
 * 示例 3：
 * 输入：n = 50
 * 输出：564908303
 *
 * @author jishenghuang
 * @version 20250413
 */
public class CountGoodNums_1922 {
    static int mod = (int) 1e9 + 7;

    /**
     * Even indices should have even digit. Odd indices should have prime number
     *
     * @param n is the length of the good numbers
     * @return the number of the good numbers
     */
    public static int countGoodNumbers(long n) {
        long odd = n / 2;
        long even = (n + 1) / 2;

        return (int) (pow(5, even) * pow(4, odd) % mod);
    }

    /**
     * pow is the helper method to the number of good numbers
     *
     * @param x 5 or 4
     * @param n the number of appearance of the digit
     * @return total appearance
     */
    public static long pow(long x, long n) {
        // Base case for recursion
        if (n == 0) {
            return 1;
        }

        // Recursively calculate x ^ (n / 2)
        long temp = pow(x, n / 2);

        // If n is even, return (x ^ (n / 2)) ^ 2
        if (n % 2 == 0) {
            return (temp * temp) % mod;
        } else {
            // If n is odd, return (x ^ (n / 2)) ^ 2 * x;
            return (x * temp * temp) % mod;
        }
    }

    /**
     * Main method
     *
     * @param args is the arguments
     */
    public static void main(String[] args) {
        System.out.println(countGoodNumbers(1));    // 5
        System.out.println(countGoodNumbers(4));    // 400
        System.out.println(countGoodNumbers(50));   // 564908303
    }
}
